// 字符串(主串/多模式串)匹配，多模式匹配 不仅限于字符串

/*
AC自动机可用于敏感词过滤

步骤：
一、预处理：多模式串创建一个Trie树，然后对每个节点计算失败指针（类似KMP算法的next数组）。结果就是AC自动机
  abc的失败指针指向bc，bc是abc后缀能匹配的最长模式串
二、匹配：遍历主串，到每个字符都去AC自动机查找是否存在匹配串。时间复杂度近似于O(n)，n是主串长度
*/

struct AcNode {
  char data;
  AcNode* children;   // 字符集只包含a~z这26个字符
  bool isEndingChar;  // 结尾字符为true
  int length;         // 当isEndingChar=true时，记录模式串长度
  AcNode* fail;       // 失败指针

  AcNode() { data = 0; }
  AcNode(char data) {
    data = data;
    children = new AcNode[26];
  }
};

int main() { return 0; }